package alo.p10;

import org.junit.Test;

import java.util.Arrays;

/**
 * @ClassName MergeSort
 * @Description TODO
 * @Author Fanxc
 * @DATE 2021/3/11 15:13
 * @Version 1.0
 */
public class MergeSort {
    //自顶向下
    void mergeSort(int[] A, int[] temp,int left, int right){
        if (left>=right){
            return;
        }

        int mid=left+(right-left)/2;
        mergeSort(A,temp,left,mid);
        mergeSort(A,temp,mid+1,right);
        merge(A, temp,left,mid,right);
    }
    //自底向下
    void mergeSort2(int[] A, int left, int right){
        int N=right - left + 1;
        int[] temp = new int[N];
        for (int sz=1;sz<N;sz=sz+sz){//sz子数组大小
            for (int lo=0;lo<N-sz;lo+=sz+sz){//lo：子数组索引
                merge(A,temp,lo,lo+sz-1,Math.min(lo+sz+sz-1,N-1));
            }
        }
    }

    void merge(int[] a,int[] temp, int left, int mid, int right) {
        int j=left;//左指针
        int k=mid+1;//右指针
        for (int i = left; i <= right; i++) {
            temp[i]=a[i];
        }
        for (int i = left; i <=right; i++) {
            if (j>mid){//左数组全部归并后，直接把右边数组剩余复制即可
                a[i]=temp[k++];
            }else if (k>right){//右数组全部归并后，直接把左边数组剩余复制即可
                a[i]=temp[j++];
            }else if (temp[k]<temp[j]){//左指针小于右指针，把左边的复制
                a[i]=temp[k++];
            }else {//右指针小于左指针，把右边的复制
                a[i]=temp[j++];
            }

        }
    }
    @Test
    public void test(){
        int[] arr={5,4,3,1,2};
        int[] temp = new int[arr.length];
        mergeSort(arr, temp,0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}
